队列(Queue)是一种运算受限的线性表,特点:先进先出。(FIFO:First In First Out)
受限之处:
- 只允许在表的前端(front)进行删除操作。
- 只允许在表的后端(rear)进行插入操作。
生活中类似队列结构的场景:
- 排队,比如在电影院,商场,甚至是厕所排队。
- 优先排队的人,优先处理。 (买票、结账、WC)。
队列的应用:
- 打印队列:计算机打印多个文件的时候,需要排队打印;
- 线程队列:当开启多线程时,当新开启的线程所需的资源不足时就先放入线程队列,等待CPU处理;
# 1、队列封装
队列的实现和栈一样,有多种方案:
- 基于数组实现。(效率低)
- 基于链表实现。
队列常见的操作:
enqueue(element)
向队列尾部添加一个(或多个)新的项。dequeue()
移除队列的第一(即排在队列最前面的)项,并返回被移除的元素。peek()
返回队列中的第一个元素——最先被添加,也将是最先被移除的元素。队列不做任何变动(不移除元素,只返回元素信息与Stack类的peek方法非常类似)。该方法在其他语言中也可以叫作front方法。isEmpty()
如果队列中不包含任何元素,返回 true,否则返回 false。size()
返回队列包含的元素个数,与数组的 length 属性类似。toString()
将队列中的内容,转成字符串形式。
// 基于数组封装队列类
class Queue {
constructor() {
this.items = [];
}
// 方法
// 1.enqueue():将元素加入到队列中
enqueue = element => {
this.items.push(element)
}
// 2.dequeue():从队列中删除前端元素
dequeue = () => {
return this.items.shift()
}
// 3.front():查看前端的元素
front = () => {
return this.items[0]
}
// 4.isEmpty:查看队列是否为空
isEmpty = () => {
return this.items.length == 0;
}
// 5.size():查看队列中元素的个数
size = () => {
return this.items.length
}
// 6.toString():将队列中元素以字符串形式输出
toString = () => {
let resultString = ''
for (let i of this.items){
resultString += i + ' '
}
return resultString
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
测试结果:
// enqueue() 测试
queue.enqueue('a1212');
queue.enqueue('b');
queue.enqueue('c');
queue.enqueue('d');
console.log(queue.toString()); //--> a,b,c,d
// dequeue() 测试
queue.dequeue();
queue.dequeue();
console.log(queue.toString()); //--> c,d
// peek() 测试
console.log(queue.peek()); //--> c
// isEmpty() 测试
console.log(queue.isEmpty()); //--> false
// size() 测试
console.log(queue.size()); //--> 2
// toString() 测试
console.log(queue.toString()); //--> c d
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 2、队列应用
使用队列实现小游戏:
击鼓传花,传入一组数据和设定的数字num,循环遍历数组内元素,遍历到的元素为数字num所指的元素时将该元素删除,直至数组剩下一个元素。
分析:
- 这里用队列比较好,先把所有参与的人按顺序加入到队列中,之后从头开始计数
- 没有数到相应数字的人从前端出队后再从后端入队
- 数到相应数字的人出队不再入队
- 不断重复这个流程直到只剩下一人,找出该人在原来队列中索引即可。
// 队列应用:面试题:击鼓传花
let passGame = (nameList, num) => {
//1.创建队列结构
let queue = new Queue();
//2.将所有人依次加入队列
// 这是ES6的for循环写法,i相当于nameList[i]
for (let i of nameList) {
queue.enqueue(i);
}
// 3.开始数数
while (queue.size() > 1) {
//队列中只剩1个人就停止数数
//不是num的时候,重新加入队列末尾
//是num的时候,将其从队列中删除
// 3.1.num数字之前的人重新放入队列的末尾(把队列前面删除的加到队列最后)
for (let i = 0; i < num - 1; i++) {
queue.enqueue(queue.dequeue());
}
// 3.2.num对应这个人,直接从队列中删除
/*
思路是这样的,由于队列没有像数组一样的下标值不能直接取到某一元素,
所以采用,把num前面的num-1个元素先删除后添加到队列末尾,
这样第num个元素就排到了队列的最前面,可以直接使用dequeue方法进行删除
*/
queue.dequeue();
}
//4.获取剩下的那个人
console.log("queue.size()", queue.size()); //1
let endName = queue.peek();
console.log("最终剩下的人:" + endName); ///Yilei
return nameList.indexOf(endName);
};
//测试击鼓传花
let names = ["lily", "Nucy", "Tom", "Yilei", "Tony"];
passGame(names, 3); //Yilei
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# 3、优先队列(PriorityQueue)
生活中类似优先级队列的场景:
- 优先排队的人,优先处理。 (买票、结账、WC)。
- 排队中,有紧急情况(特殊情况)的人可优先处理。
计算机中优先级队列的应用场景:
- 每个线程处理的任务重要性不同,我们可以通过优先级的大小,来决定该线程在队列中被处理的次序
优先级队列主要考虑的问题为:
- 每个元素不再只是一个数据,还包含数据的优先级;
- 在添加数据过程中,根据优先级放入到正确位置;
# 4、封装优先级队列
// 优先队列内部的元素类
// 注意js是不能直接在class中声明class的,得单独声明两个类
class QueueElement {
constructor(element, priority) {
this.element = element;
this.priority = priority;
}
}
// 优先队列类(继承 Queue 类)
class PriorityQueue extends Queue {
constructor() {
console.log("77777777");
super();
}
// enqueue(element, priority) 入队,将元素按优先级加入到队列中
// 重写 enqueue()
enqueue=(element, priority)=> {
// 根据传入的元素,创建 QueueElement 对象
const queueElement = new QueueElement(element, priority);
// 判断队列是否为空
if (this.isEmpty()) {
// 如果为空,不用判断优先级,直接添加
this.items.push(queueElement);
} else {
// 定义一个变量记录是否成功添加了新元素
let added = false;
for (let i = 0; i < this.items.length; i++) {
// 让新插入的元素进行优先级比较,priority 值越小,优先级越大
if (queueElement.priority < this.items[i].priority) {
// 在指定的位置插入元素
this.items.splice(i, 0, queueElement);
added = true;
break;
}
}
// 如果遍历完所有元素,优先级都大于新插入的元素,就将新插入的元素插入到最后
if (!added) {
this.items.push(queueElement);
}
}
}
// 其余父类中的方法直接使用即可
// toString() 将队列中元素以字符串形式返回
// 重写 toString()
toString=()=> {
let result = "";
for (let item of this.items) {
result += item.element + "-" + item.priority + " ";
}
return result;
}
}
//测试
const priorityQueue = new PriorityQueue();
// 入队 enqueue() 测试
priorityQueue.enqueue("A", 10);
priorityQueue.enqueue("B", 15);
priorityQueue.enqueue("C", 11);
priorityQueue.enqueue("D", 20);
priorityQueue.enqueue("E", 18);
console.log(priorityQueue.toString());
//--> output:
// A-10 C-11 B-15 E-18 D-20
// 出队 dequeue() 测试
priorityQueue.dequeue();
priorityQueue.dequeue();
console.log(priorityQueue.toString());
//--> output:
// B-15 E-18 D-20
// isEmpty() 测试
console.log(priorityQueue.isEmpty()); //--> false
// size() 测试
console.log(priorityQueue.size()); //--> 3
// toString() 测试
console.log(priorityQueue.toString()); //--> B-15 E-18 D-20
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
在父类使用箭头函数,子类使用传统函数时,子类实例会调用父类方法。
这是因为,在类中用=
赋值就会挂载到实例上。
class Test {
t1 = 't1';
t2 = () => {
console.log('t2');
}
t3() {
console.log('t3');
}
}
console.log(Test.prototype);
console.log(new Test()); //t2会挂载在实例上 t3不会
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11